/* File:
 * Author:
 * Description:
 */

template <class T, unsigned int N>
void DIRECTED_GRAPH<T,N>::clear()
{
  if(m_vData != NULL && m_adjMatrix != NULL)
  {
    for(int i=0; i<N; i++)
    {
      delete [] m_adjMatrix[i];//really not sure about this
    }
    delete [] m_adjMatrix;
    delete [] m_vData;
    m_adjMatrix=NULL;
    m_vData=NULL;
    COLLECTION<T>::m_size=0;
  }
}

template <class T, unsigned int N>
bool DIRECTED_GRAPH<T,N>::isEdge(const unsigned int i, const unsigned int j) const
{
  if(i >= N || j >= N)
  {
    throw std::out_of_range("Out of range");
  }
  return m_adjMatrix[i][j] != 0;
}

template <class T, unsigned int N>
bool DIRECTED_GRAPH<T,N>::find(const T& x) const
{
  for(int i=0; i<N; i++)
  {
    if(x==m_vData[i])
    {
      return true;
    }
  }
  return false;
}

template <class T, unsigned int N>
void DIRECTED_GRAPH<T,N>::setVertexData(const unsigned int i, const T& data)
{
  if(i>=N)
  {
    throw std::out_of_range("Out of range");
  }
  m_vData[i]=data;
}

template <class T, unsigned int N>
T DIRECTED_GRAPH<T,N>::getVertexData(const unsigned int i) const
{
  if(i>=N)
  {
    throw std::out_of_range("Out of range");
  }
  return m_vData[i];
}

template <class T, unsigned int N>
int DIRECTED_GRAPH<T,N>::getEdgeWeight(const unsigned int i, const unsigned int j) const
{
  if(i >= N || j >= N)
  {
    throw std::out_of_range("Out of range");
  }
  return m_adjMatrix[i][j];
}

template <class T, unsigned int N>
void DIRECTED_GRAPH<T,N>::setEdgeWeight(const unsigned int i, const unsigned int j, const int w)
{
  if(i >= N || j >= N)
  {
    throw std::out_of_range("Out of range");
  }
  m_adjMatrix[i][j] = w;//This is exactly the same as addEdge. is this correct?
}

template <class T, unsigned int N>
void DIRECTED_GRAPH<T,N>::removeEdge(const unsigned int i, const unsigned int j)
{
  if(i >= N || j >= N)
  {
    throw std::out_of_range("Out of range");
  }
  m_adjMatrix[i][j] = 0;
}

template <class T, unsigned int N>
int DIRECTED_GRAPH<T,N>::vertexInDegree(const unsigned int i) const
{
  int count=0;
  if(i>=N)
  {
    throw std::out_of_range("Out of range");
  }
  for(int j=0; j<N; j++)
  {
    if(m_adjMatrix[j][i] != 0)
    {
      count++;
    }
  }
  return count;
}

template <class T, unsigned int N>
int DIRECTED_GRAPH<T,N>::vertexOutDegree(const unsigned int i) const
{
  int count=0;
  if(i>=N)
  {
    throw std::out_of_range("Out of range");
  }
  for(int j=0; j<N; j++)
  {
    if(m_adjMatrix[i][j] != 0)
    {
      count++;
    }
  }
  return count;
}

template <class T, unsigned int N>
int DIRECTED_GRAPH<T,N>::graphDegree() const
{
   int count=0;
   for(int i=0; i<N; i++)
   {
     count+=vertexOutDegree(i)+vertexInDegree(i);
   }
  return count;
}

template <class T, unsigned int N>
bool DIRECTED_GRAPH<T,N>::operator==(const DIRECTED_GRAPH<T, N>& rhs) const
{
  if(COLLECTION<T>::size() != rhs.COLLECTION<T>::size())
    return false;
  for(int i=0; i<N; i++)
  {
     if(getVertexData(i) != rhs.getVertexData(i))
       return false;
     for(int j=0; j<N; j++)
     {
       if(getEdgeWeight(i,j) != rhs.getEdgeWeight(i,j))
         return false;
     }
  }
  return true;
}

template <class T, unsigned int N>
bool DIRECTED_GRAPH<T,N>::isAcyclic() const  
{
  //first check for parallel lines
  for(int i=0; i<N; i++)
  {
    for(int j=0; j<N; j++)
    {
      if( m_adjMatrix[i][j]* m_adjMatrix[j][i] != 0)
        return false;
    }
  }

  //check for points connected to themselves
  for(int i=0; i<N; i++)
  {
    if(m_adjMatrix[i][i] != 0)
    {
      return false;
    }
  }
  
  //then check for other loops
  int foundArray[N];

  for(int i=0; i<N; i++)
  {
    for(int i=0; i<N; i++)
    {
      foundArray[i]=-1;
    }
    if(loopFinder(0, foundArray, true))
    {
      return false;
    }
  }
  return true;
}

template <class T, unsigned int N>
bool DIRECTED_GRAPH<T,N>::loopFinder(const int currentPos, int foundArray[],  bool firstIteration) const
{
  bool loopFound=false;
  for(int i=0; i<N; i++)
  {
    if(currentPos==foundArray[i])
      loopFound=true;
  }
  if(loopFound && !firstIteration)
  {
    return true;
  }
  for(int i=0; i<N; i++)
  {
    if(m_adjMatrix[currentPos][i] != 0)
    {
      int counter=0;
      while(counter<N)//add the number of the visited node to the array
      {
        if(foundArray[counter]==-1)
        {
          foundArray[counter]=currentPos;
          counter=N;
        }
        counter++;
      }
      if(loopFinder(i, foundArray))
      {
        return true;
      }
    }
  }
  return false;
}

template <class T, unsigned int N>
bool DIRECTED_GRAPH<T,N>::isComplete() const
{
  if(N==0)
    return true;
  if(!isSimple())
    return false;
  
  //calculate how many lines there should be in order to be complete assuming it is simple
  int numb=N-1;
  for(int i=N-2; i>0; i--)
  {
    numb+=i;
  }
  
  //count how many lines there are in the graph
  int actualCount=0;
  for(int i=0; i<N; i++)
  {
    for(int j=0; j<N; j++)
    {
       if(m_adjMatrix[i][j] != 0)
       {
         actualCount++;
       }
    }
  }
  return  actualCount==numb;
}

template <class T, unsigned int N>
bool DIRECTED_GRAPH<T,N>::isSimple() const
{
  //first check for parallel lines
  for(int i=0; i<N; i++)
  {
    for(int j=0; j<N; j++)
    {
      if( m_adjMatrix[i][j]* m_adjMatrix[j][i] != 0)
        return false;
    }
  }
  //check for points connected to themselves
  for(int i=0; i<N; i++)
  {
    if(m_adjMatrix[i][i] != 0)
    {
      return false;
    }
  }
  return true;
}
































